1180. Count Substrings with Only One Distinct Letter
Easy

Given a string s, return the number of substrings that have only one distinct letter.

 

Example 1:

Input: s = "aaaba"
Output: 8
Explanation: The substrings with one distinct letter are "aaa", "aa", "a", "b".
"aaa" occurs 1 time.
"aa" occurs 2 times.
"a" occurs 4 times.
"b" occurs 1 time.
So the answer is 1 + 2 + 4 + 1 = 8.

Example 2:

Input: s = "aaaaaaaaaa"
Output: 55

 

Constraints:

  • 1 <= s.length <= 1000
  • s[i] consists of only lowercase English letters.
Accepted
16.3K
Submissions
20.9K
Seen this question in a real interview before?
Companies
Related Topics
Show Hint 1
What if we divide the string into substrings containing only one distinct character with maximal lengths?
Show Hint 2
Now that you have sub-strings with only one distinct character, Try to come up with a formula that counts the number of its sub-strings.
Show Hint 3
Alternatively, Observe that the constraints are small so you can use brute force.

Average Rating: 5.00 (6 votes)

Premium

Solution


Approach 1: Arithmetic Sequence

Intuition

Note that given a string s, there are:

  • substrings with size 1: len(s);

  • substrings with size 2: len(s) - 1;

    ...

  • substrings with size len(s) - 1: 2;

  • substrings with size len(s): 1.

Therefore, the number of substrings of s is 1 + 2 + ... + (len(s) - 1) + len(s), which is an Arithmetic Sequence. If you are familiar with the Sum Equation of Arithmetic Sequence, it's obvious that the number of substrings is (1 + len(s)) * len(s) / 2. If not, I'll also provide a rough analysis here for your reference.

Given a list of numbers 1, 2, 3, ..., n-1, n, an interesting fact is that:

  • 1 + n = n + 1
  • 2 + (n - 1) = n + 1
  • 3 + (n - 2) = n + 1
  • ...

If n is an even number, there would be n / 2 pairs of numbers summed to n + 1. Hence the sum of all numbers is simply (1 + n) * n / 2. Moreover, this applies to cases when n is an odd number!

Notice that, if a string contains only one distinct letter, all of its substrings are formed by one distinct letter as well. For example, all substrings of aaa contain only one distinct letter a: a, aa, and aaa. Therefore, to find the number of substrings that contain only one distinct letter, we can first find the longest continuous segments with only one distinct letter; then we can apply the formula mentioned above to calculate the number of substrings of each segment.

Recursion Tree Figure

Figure 1. Find the longest continuous segments with one distinct letter and count the substrings.

Algorithm

  • Initialize an integer variable total to count the number of substrings along with the iteration; initialize two pointers left and right which mark the beginning and the end of the substring that contains only one distinct letter.
  • Iterate through S:
    • If we do not reach the end and the new character S[right] is the same as the beginning one S[left], increment right by 1 to keep exploring S;
    • otherwise, calculate the length of the substring as right - left and apply the Sum Equation of Arithmetic Sequence; remember to set right as left to start exploring the new substring.

Complexity Analysis

  • Time Complexity: O(N)\mathcal{O}(N), where NN is the length of S. This is because we iterate through S once.
  • Space Complexity: O(1)\mathcal{O}(1). This is because we do not use additional data structures.

Approach 2: Dynamic Programming

Intuition

Given a string S, we may define an integer array substrings[] with a length of len(S), such that substrings[i] is the number of substrings ending with S[i] which contains only one distinct letter S[i]. Therefore, if S[i] == S[i - 1], substrings[i] would be substrings[i - 1] + 1 where 1 refers to the substring containing only S[i]; else if S[i] != S[i - 1], substrings[i] would be 1.

Current
1 / 10

For those who like mathematical definitions, you may find the state transition function as follows. Otherwise, feel free to skip this part.

substrings(i)={substrings(i1)+1,if S[i1]==S[i]1,otherwise \text{substrings}(i)=\begin{cases} \text{substrings}(i - 1) + 1, & \text{if $\text{S}[i - 1] == \text{S}[i]$}\\ 1, & \text{otherwise} \end{cases}

Algorithm

  • Initialize an integer total to count the number of substrings during the iteration, and an integer array substrings to record the number of substrings ending with S[i] containing only one distinct letter S[i].
  • Initialize substrings[0] to 1.
  • Iterate S skipping the first element as we've initialized substrings[0]:
    • if S[i-1] == S[i], set substrings[i] to substrings[i-1] + 1;
    • else, set substring[i] to 1.
    • increment total by substrings[i].

Note that substrings[i] only depends on substrings[i - 1], therefore instead of using an array, we can use an integer variable count to keep track of substrings[i] to improve the space complexity from O(N)\mathcal{O}(N) to O(1)\mathcal{O}(1).

Complexity Analysis

  • Time Complexity: O(N)\mathcal{O}(N), where NN is the length of S. This is because we iterate through S once.
  • Space Complexity: O(1)\mathcal{O}(1). The original implementation of this dynamic programming approach takes O(N)\mathcal{O}(N) space complexity as it uses an array with a size of len(S). With the optimization, we achieve O(1)\mathcal{O}(1) space complexity because we do not use additional data structures.

Report Article Issue

Comments: 1

You don't have any submissions yet.

/23
Contribute
|||
Saved
Trie
#208 Implement Trie (Prefix Tree)
Medium
#211 Design Add and Search Words Data Structure
Medium
#212 Word Search II
Hard
#336 Palindrome Pairs
Hard
#421 Maximum XOR of Two Numbers in an Array
Medium
#425 Word Squares
Hard
#472 Concatenated Words
Hard
#642 Design Search Autocomplete System
Hard
#648 Replace Words
Medium
#676 Implement Magic Dictionary
Medium
#677 Map Sum Pairs
Medium
#692 Top K Frequent Words
Medium
#720 Longest Word in Dictionary
Easy
#745 Prefix and Suffix Search
Hard
#1023 Camelcase Matching
Medium
#1032 Stream of Characters
Hard
#1065 Index Pairs of a String
Easy
#1638 Count Substrings That Differ by One Character
Medium
#1698 Number of Distinct Substrings in a String
Medium
#1707 Maximum XOR With an Element From Array
Hard
#1803 Count Pairs With XOR in a Range
Hard
#1804 Implement Trie II (Prefix Tree)
Medium
#1858 Longest Word With All Prefixes
Medium